package com.mango.leet.code.easy;

/**
 * 1486. 数组异或操作
 */
/**
 * 给你两个整数，n 和 start 。
 *
 * 数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
 *
 * 请返回 nums 中所有元素按位异或（XOR）后得到的结果。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 5, start = 0
 * 输出：8
 * 解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
 *      "^" 为按位异或 XOR 运算符。
 * 示例 2：
 *
 * 输入：n = 4, start = 3
 * 输出：8
 * 解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.
 * 示例 3：
 *
 * 输入：n = 1, start = 7
 * 输出：7
 * 示例 4：
 *
 * 输入：n = 10, start = 5
 * 输出：2
 *  
 *
 * 提示：
 *
 * 1 <= n <= 1000
 * 0 <= start <= 1000
 * n == nums.length
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xor-operation-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * @Author: mango
 * @Date: 2022/3/26 10:09 下午
 */
public class LC1486_XOROperationArray {
    class Solution {
        // O(n)
        public int xorOperation(int n, int start) {
            int eor = 0;
            for(int i=0;i<n;i++){
                eor ^= start + 2 * i;
            }
            return eor;
        }
        // O(1)
        public int xorOperation2(int n, int start) {
            // start 右移动1位
            int s = start >> 1;
            /**
             * 原来式子：ret = start ^ (start+2) ^ (start+4) ^ ... ^ (start+2(n-1))
             * 除以2后：ret>>1 = s ^ (s+1) ^ (s+2) ^ ... ^ (s+n-1)，其中s=start/2
             *
             */
            int e = n & start & 1;
            int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
            return ret << 1 | e;
        }
        // 0^1^2^3=0
        // 4^5^6^7=0
        public int sumXor(int x) {
            if (x % 4 == 0) {
                return x;
            }
            if (x % 4 == 1) {
                return 1;
            }
            if (x % 4 == 2) {
                return x + 1;
            }
            return 0;
        }
    }
}
